package visualizer.client.algorithms.bst;

import visualizer.client.algorithms.AlgoResult;
import visualizer.client.algorithms.Algorithm;
import visualizer.client.bst.BNode;
import visualizer.client.bst.BinaryTree;

/**
 * User: DDovzhenko
 * Date: 07.01.14
 * Time: 18:25
 */
public class BSTSearchingAlgorithm implements Algorithm {
    private int totalStepCount;

    @Override
    public AlgoResult performAlgorithmToStep(BinaryTree tree, int step, int inputValue) {
        return searchInBST(tree.copyTree(false), inputValue, step);
    }

    @Override
    public int getStepsCount(BinaryTree tree, int inputValue) {
        totalStepCount = 0;
        searchInBST(tree.copyTree(false), inputValue, -1);
        return totalStepCount;
    }

    private AlgoResult searchInBST(BinaryTree bTree, int value, int stepNo) {
        BNode searchNode = new BNode(value);
        if (stepNo-- == 0) {
            return new AlgoResult(bTree, "Поиск узла с ключом " + searchNode.getValue());
        }
        BNode theRootNode = bTree.getRoot();
        if (theRootNode == null) {
            updateTotalStepCount(stepNo);
            return new AlgoResult(bTree, "Дерево пусто, узла с ключом " + searchNode.getValue() + " не существует");
        }
        while (true) {
            if (searchNode.getValue().compareTo(theRootNode.getValue()) == 0) {
                updateTotalStepCount(stepNo);
                theRootNode.setInnerColor("lightgreen");
                theRootNode.setOuterColor("green");
                return new AlgoResult(bTree, "Узел с ключом " + searchNode.getValue() + " найден");
            } else if (searchNode.getValue().compareTo(theRootNode.getValue()) < 0) {
                if (stepNo-- == 0) {
                    theRootNode.setOuterColor("red");
                    return new AlgoResult(bTree, "Сравниваем ключи в узлах: ключ " + searchNode.getValue() + " меньше ключа " + theRootNode.getValue() + ", обрабатываем левое поддерево");
                }
                if (theRootNode.getLeftBNode() == null) {
                    if (stepNo-- == 0) {
                        theRootNode.setOuterColor("red");
                        return new AlgoResult(bTree, "У узла нет левого потомка, узла с ключом " + searchNode.getValue() + " не существует");
                    }
                    updateTotalStepCount(stepNo);
                    return new AlgoResult(bTree, "Узла с ключом " + searchNode.getValue() + " не существует");
                }
                theRootNode = theRootNode.getLeftBNode();
            } else {
                if (stepNo-- == 0) {
                    theRootNode.setOuterColor("red");
                    return new AlgoResult(bTree, "Сравниваем ключи в узлах: ключ  " + searchNode.getValue() + " больше ключа " + theRootNode.getValue() + ", обрабатываем правое поддерево");
                }
                if (theRootNode.getRightBNode() == null) {
                    if (stepNo-- == 0) {
                        theRootNode.setOuterColor("red");
                        return new AlgoResult(bTree, "У узла нет правого потомка, узла с ключом " + searchNode.getValue() + " не существует");
                    }
                    updateTotalStepCount(stepNo);
                    return new AlgoResult(bTree, "Узла с ключом " + searchNode.getValue() + " не существует");
                }
                theRootNode = theRootNode.getRightBNode();
            }
        }
    }

    private void updateTotalStepCount(int stepNo) {
        if (stepNo < 0) {
            totalStepCount = -stepNo;
        }
    }
}
